1. Field of the Invention
This invention relates to computer systems and, more particularly, to circuitry for sorting among end points of line segments to be displayed on the output display of a computer system.
2. History of the Prior Art
A major problem in utilizing computers to provide graphic displays is that for a single frame of graphical material to be presented on a cathode ray tube (CRT), it is usually necessary to store an indication of the information which is to be displayed for each position (pixel) of the cathode ray tube. With large and detailed displays, the number of pixels on the cathode ray tube may be approximately one thousand or greater in a horizontal direction and a like number in the vertical direction giving a total of approximately one million or more pixels about which information is to be stored. In a preferred system which is capable of providing a number of different colors on the cathode ray tube, each of these pixels contains eight bits of digital information specifying the particular color output. Consequently, approximately eight million bits of information need to be stored for each frame to be presented at the output.
Not only does color information have to be provided for each pixel for each frame of the display, but in generating graphic displays, the usual method of determining the shapes of figures requires that various algorithms be applied to the data to shape those figures. If this information is handled by the software of the system, computing the positions of each point to be displayed and determining the data to be displayed at that point slows the operation of the system to a point where functions such as animation are essentially impossible. For example, in order to present a polygon on the output display, it is necessary to determine each end on each horizontal line which makes up the polygon because the information is furnished to the display by scan lines. In prior art systems, this determination of the ends of each line to be scanned to the output display required the use of software run by the central processing unit (CPU) to evaluate the end values for each scan line of each graphical shape to be presented. Such arrangements increase the time taken to present the graphics to a point where appreciable slowing of the display occurs.
For this reason, various systems utilizing hardware to speed the operation have been suggested. One method for speeding the operation uses two output frame buffers and loads one buffer while the other is being scanned to the display. Such a system significantly speeds the operation but requires essentially twice as much memory to accomplish the storage.
There has now been proposed a unique system for presenting computer graphics on an output display using only a single output frame buffer. The system breaks all graphics shapes into quadrilaterals, then decomposes the quadrilaterals into subportions subtended by line segments which provide a trapezoidal area of scan lines to be displayed. By breaking the shapes into quadrilaterals, each point, line, triangle, and quadrilateral may be handled in the same manner to speed the operation of the circuit. Moreover, the system allows the information to be scanned to the frame buffer from top to bottom, in reverse, from left to right, or in reverse to further increase the speed of operation because of the ability to eliminate certain page mode jumps and to scan only the information to the frame buffer which need not be clipped thereby eliminating the loss of time in clipping.
Normally, the information to be displayed is transferred to the input of the circuitry for scanning to the frame buffer in a consistent manner. That is, the information transferred first is that which is to be first presented. The information is transferred from the top of the display down and from left to right. This is not the manner in which the system of which the present invention is a part handles the information prior to the time of transfer to the frame buffer. Consequently, some arrangement must be provided for sorting the information available for storage by the frame buffer which arrangement operates to accomplish the sorting without appreciable delay.
It is, therefore, an object of the present invention to speed the operation of computer systems.
It is another object of the present invention to provide circuitry for handling in hardware the manipulations of graphical material which have in the usual case been handled by the software of the computer system.
It is an additional object of the present invention to provide circuitry for sorting among the addressing information provided for storage of images by a frame buffer to determining the X and Y coordinates of the ends of lines to be scanned to the frame buffer for presentation by the output display.
It is an additional object of the present invention to provide circuitry for sorting among the addressing information provided for storage of images by a frame buffer to determining the X and Y coordinates of the ends of lines to be scanned to the frame buffer for presentation by the output display particularly in view of the clip window in which the information is to appear.